#leetcode题目60：排列序列
#难度：困难
#时间复杂度：O(n!)
#空间复杂度：O(n)

#方法：回溯

#根据前缀出现次数来计算出下一个排列

from typing import List

class Solution:
    # def getPermutation(self, n: int, k: int) -> str:
    #     res=[]
    #     def dfs(n,k,path):
    #         if not n:
    #             res.append(path)
    #             return
    #         for i in range(1,n+1):
    #             if i in path:
    #                 continue
    #             dfs(n-1,k-1,path+str(i))
    #     dfs(n,k,"")
    #     return res[k-1]

    #方法二：视频解法，根据出现的规律
    def getPermutation(self, n: int, k: int) -> str:
        factorial=[1,1]
        for i in range(2,n+1):
            factorial.append(factorial[-1]*i)
        res=''
        s=[i for i in range(1,n+1)]
        for i in range(len(s)-1,-1,-1):
            res+=str(s[(k-1)//factorial[i]])
            del s[(k-1)//factorial[i]]
            k%=factorial[i]
        return res


#测试数据
n=3
k=3
#预期输出："213"
solution=Solution()
print(solution.getPermutation(n,k))

n=4
k=9
#预期输出："2314"
solution=Solution()
print(solution.getPermutation(n,k))

n=3
k=1
#预期输出："123"
solution=Solution()
print(solution.getPermutation(n,k))

        
        